Background: Flux Balance Analysis (FBA) is a genome-scale computational technique for modeling the steady-state\nfluxes of an organism�s reaction network. When the organism�s reaction network needs to be completed to obtain\ngrowth using FBA, without relying on the genome, the completion process is called reaction gap-filling. Currently,\ncomputational techniques used to gap-fill a reaction network compute the minimum set of reactions using\nMixed-Integer Linear Programming (MILP). Depending on the number of candidate reactions used to complete the\nmodel, MILP can be computationally demanding.\nResults: We present a computational technique, called FastGapFilling, that efficiently completes a reaction network\nby using only Linear Programming, not MILP. FastGapFilling creates a linear program with all candidate reactions, an\nobjective function based on their weighted fluxes, and a variable weight on the biomass reaction: no integer variable\nis used. A binary search is performed by modifying the weight applied to the flux of the biomass reaction, and solving\neach corresponding linear program, to try reducing the number of candidate reactions to add to the network to\ngenerate a working model. We show that this method has proved effective on a series of incomplete E. coli and yeast\nmodels with, in some cases, a three orders of magnitude execution speedup compared with MILP. We have\nimplemented FastGapFilling in MetaFlux as part of Pathway Tools (version 17.5), which is freely available to academic\nusers, and for a fee to commercial users. Download from: biocyc.org/download.shtml.\nConclusions: The computational technique presented is very efficient allowing interactive completion of reaction\nnetworks of FBA models. Computational techniques based on MILP cannot offer such fast and interactive completion.
Loading....